package com.xcc.datastructure;


import java.util.*;

/**
 * @Description 求【无重复字符的最长子串】练习
 *
 * 题目描述：
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * <p>
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s由英文字母、数字、符号和空格组成
 *
 * @Author xiechuang
 * @Date 2022/11/14
 */
public class NoRepeateMaxChildStrDemo {

    public static void main(String[] args) {

        // 预期结果：3
        System.out.println("v1：" + noRepeateMaxChildStrV1("abcabcbb"));
        System.out.println("v2：" + noRepeateMaxChildStrV2("abcabcbb"));

        // 预期结果：1
        System.out.println("v1：" + noRepeateMaxChildStrV1("bbbbb"));
        System.out.println("v2：" + noRepeateMaxChildStrV2("bbbbb"));

        // 预期结果：3
        System.out.println("v1：" + noRepeateMaxChildStrV1("pwwkew"));
        System.out.println("v2：" + noRepeateMaxChildStrV2("pwwkew"));

        // 预期结果：1
        System.out.println("v1：" + noRepeateMaxChildStrV1(" "));
        System.out.println("v2：" + noRepeateMaxChildStrV2(" "));

        // 预期结果：2
        System.out.println("v1：" + noRepeateMaxChildStrV1("au"));
        System.out.println("v2：" + noRepeateMaxChildStrV2("au"));

    }

    /**
     * 版本二：
     * 思路：两层遍历使用set集合验证是否有重复元素
     *
     * @param s
     * @return
     */
    public static int noRepeateMaxChildStrV1(String s) {
        int length = 0;
        int sLength = s.length();
        if (sLength > 1) {
            for (int i = 0; i < sLength-1; i++) {
                char c1 = s.charAt(i);
                Set<Character> set = new HashSet<>();
                set.add(c1);
                for (int j = i + 1; j < sLength; j++) {
                    char c2 = s.charAt(j);
                    int len1 = set.size();
                    set.add(c2);
                    int len2 = set.size();
                    length = Math.max(length, len2);
                    if (len1 == len2) {
                        break;
                    }
                }
            }
        } else {
            length = sLength;
        }
        return length;
    }

    /**
     * 版本二：
     * 思路：使用队列，判断当前元素在对列中是否存在，如果不存在则假如队列，如果存在就遍历移除头部元素直到不存在当前元素，将当前元素加入队列继续遍历
     *
     * @param s
     * @return
     */
    public static int noRepeateMaxChildStrV2(String s) {
        int length = 0;
        int sLength = s.length();
        // 队列存储元素
        Queue<Character> queue = new ArrayDeque<>();
        for(int i = 0; i < sLength; i++) {
            // 当前元素
            char c1 = s.charAt(i);
            // 如果当前元素在队列中有值则移除队列中该值包括之前所有的值：例如队列值 [a,b,c] 当前值为b,则最终队列值为[c]
            while (queue.size() > 0 && queue.contains(c1)) {
                queue.poll();
            }
            // 添加元素
            queue.offer(c1);
            length = Math.max(length, queue.size());
        }
        return length;
    }

}
